package src.leetcode.everyday.hard_3261;

import java.util.Arrays;

public class countKConstraintSubstrings {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution().countKConstraintSubstrings("010101", 1, new int[][]{{0, 5}, {1, 4}, {2, 3}})));

    }
}
class Solution {
    public long[] countKConstraintSubstrings(String s, int k, int[][] queries) {
        int n = s.length();
        int[] dp = new int[n];
        long[] ans = new long[queries.length];

        int left = 0, right = 0;
        int[] cur = new int[2];
        while (right < n) {
            cur[s.charAt(right++) & 1]++;
            while (cur[0] > k && cur[1] > k) {
                cur[s.charAt(left++) & 1]--;
            }
            dp[right - 1] = right - left;
        }

        for (int i = 0; i < queries.length; i++) {
            int[] query = queries[i];
            for (int j = query[0]; j <= query[1]; j++) {
                ans[i] += Math.min(dp[j], j - query[0] + 1);
            }
        }

        return ans;
    }
}